#include <stdio.h>
#include <stdlib.h>
#include "sorts.h"
 
static void partition_sort(ELE_TYPE arr[], int low, int high)
{
	ELE_TYPE base;
	int left,right;
	
	if ( high-low+1 <= INSERT_SORT_THRESHOLD)
	{
		insert_sort(arr+low, high-low+1);
		return ;
	}
 
	left=low;right=high;
	base= arr[low];
	
	while (right>left)
	{
		while (right>left && arr[right]>= base)
			right--;
		
		if ( right>left)
		{	arr[left]=arr[right];	left++;}	// fill the hole, the hole is arr[left]
 
		while (left<right && arr[left]< base)
			left++;
		
		if ( left<right)
		{
			arr[right]=arr[left];	right--;	// fill the hole, the hole is arr[right]
		}
	}
 
	arr[left]=base;		// now, the left==right
	partition_sort(arr,low, left-1);
	partition_sort(arr,left+1, high);
}
 
void quick_sort(ELE_TYPE arr[], int len)
{
	partition_sort(arr,0,len-1);
}
 
void test_quick_sort()
{
	ELE_TYPE arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
	int len = (int) sizeof(arr) / sizeof(arr[0]);
	
	printf("Original data are:");
	print_array(arr, len);
 
	quick_sort(arr, len);
	printf("The data after sorted are:");
	print_array(arr, len);	
}
